//
// Created by liushuai on 2020/5/17.
//
#include "restoreIpAddresses.h"
void dfs(std::string& s,std::vector<std::string>& result,std::vector<std::string>& maybe,int start){
    if(start==s.size()&&maybe.size() == 4){//字符串被分成四段同时遍历完整个字符
        std::string ip_string = maybe[0];
        for(int index = 1;index<4;index++)
            ip_string += "."+maybe[index];
        result.push_back(ip_string);
        return;
    }
    else if(start<s.size() && maybe.size() == 4){//找到四段，但是没有到字符串末尾
        return;
    }
    else{
        for(int length=1;length<4;length++){
            if (length != 1 && s[start] == '0') //当前可选的字符长度为2,3但是第一个元素是0的是不合法情况例如 01,但是0是合法的
                return;
            else if(start>=s.size())//递归遍历结束了
                return;
            else{
                // 还在遍历，判断字符串是否合适
                int num_elem = std::atoi(s.substr(start,length).c_str());

                if(num_elem>=0 && num_elem<=255){
                    maybe.push_back(s.substr(start,length));
                    dfs(s,result,maybe,start+length);
                    maybe.pop_back();
                } else
                    return;

            }
        }
    }
}
std::vector<std::string> restoreIpAddresses(std::string s) {
    std::vector<std::string> result;
    std::vector<std::string> maybe;
    dfs(s,result,maybe,0);
    return result;

}